package BinaryTreePackage;

/**
 * @author Lzm
 * @version 1.0
 */
public class countNodes_ {

  // 确定参数和返回值
  // 确定终止条件
  // 确定每层的处理逻辑

  //如果将其当作普通的二叉树
  public int countNodes(TreeNode root) {
    if(root == null){
      return 0;
    }
    //后续遍历
    return countNodes(root.left)  + countNodes(root.right) + 1;
  }

  // 如果二叉树是一个满二叉树, 则其节点数量为 2^n - 1;
  // 如果判断一个树是完全二叉树的情况下并且是满二叉树: 左子树和右子树遍历的深度是一样的
  public int countNodes1(TreeNode root) {
    // 终止条件
    if(root == null){
      return 0;
    }
    int leftDepth = 0;
    int rightDepth = 0;
    TreeNode leftNode = root.left;
    TreeNode rightNode = root.right;
    // 左子节点一直向左遍历
    while(leftNode != null){
      leftNode = leftNode.left;
      leftDepth ++;
    }
    // 右子节点一直向左遍历
    while(rightNode != null){
      rightNode = rightNode.right;
      rightDepth ++;
    }
    // 如果子树是满二叉树则子树节点个数为 2 ^ 深度 - 1
    if (leftDepth == rightDepth){
      return 2 << leftDepth - 1;
    }
    // 左
    int leftResult = countNodes1(root.left);
    // 右
    int rightResult = countNodes1(root.right);
    // 中
    return rightResult + leftResult + 1;
  }
}
